package com.xinxin.leetcode.problem5;

import java.util.Arrays;

/**
 * @author ShiXinXin
 * @date 2019-08-31 16:47
 */
class Solution {

    public String longestPalindrome(String s) {
        if (s.isEmpty()) {
            return "";
        }
        int index = 0;
        int maxLength = 1;
        int[][] arr = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            arr[i][i] = 1;
            if (i < s.length() - 1) {
                if (s.charAt(i) == s.charAt(i + 1)) {
                    arr[i][i + 1] = 1;
                    index = i;
                    maxLength = 2;
                }
            }
        }
        for (int len = 3; len <= s.length(); len++) {
            for (int start = 0; start + len - 1 < s.length(); start++) {
                int end = start + len - 1;
                if (s.charAt(start) == s.charAt(end) && arr[start + 1][end - 1] == 1) {
                    arr[start][end] = 1;
                    index = start;
                    maxLength = len;
                }
            }
        }
        return s.substring(index, index + maxLength);
    }

    public static void main(String[] args) {
        String res = new Solution().longestPalindrome("dadcds");
        System.out.println(res);
    }
}
